package com.cheung.leetcode.list;

import lyroot.entity.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.list
 * @Author :  cheungming
 * @CreateTime : 2024-04-30 14:47:15
 * @Description : 142题
 * @Version : 1.0
 */
public class Code142 {

    /***
     * 看了题目解析：有两种算法，第一种是hash算法
     * 第二种是快慢指针
     */

    public static ListNode detectCycle(ListNode head) {
        // 保存遍历过的结点
        Set<ListNode> list = new HashSet<>();

        ListNode p = head;
        while (p != null) {
            if (list.contains(p)) {
                return p;
            } else {
                list.add(p);
            }
            p = p.next;
        }

        return null;
    }

    /**
     * 快慢指针的具体思路
     * 第一步：判断是否有环
     * 声明慢指针slow，快指针fast
     * slow每次走1步，fast走2步，如果有环则slow和fast肯定相遇
     * <p>
     * 第二步，判断环的入口
     * 按照第一步来说假设无环长度为a，有环部分长度为b，fast比slow多走了n圈
     * 则 fast = slow+nb，而fast=2slow，所以 slow = nb
     * 而每次环经过入口位置是a+nb，现在只需要求a的值
     * 现在将快指针拨回起点，和慢指针同时走1步，则快指针到第a步时，慢指针为nb+a刚好为入口
     */
    public static ListNode detectCycleV2(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;

        } while (slow != fast);

        fast = head;

        // 此处使用do while不行，do while至少会执行一次，因为当a==0时，会出现错误
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }


    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        node1.next = node2;
        node2.next = node1;


        ListNode value = detectCycleV2(node1);
        if (value == null) {
            System.out.println("null");
        } else {
            System.out.println(value.val);
        }
    }
}


